#include <stdio.h>

#include <cstddef>
#include <queue>
#include <vector>

struct ListNode {
  int val;
  ListNode *next;
  ListNode(int val, ListNode *next) : val(val), next(next) {}
  explicit ListNode(int val) : val(val), next(NULL) {}
};

class Solution {
 public:
  struct Compare {
    bool operator()(ListNode *l, ListNode *r) { return l->val > r->val; }
  };

  ListNode *mergeKLists(std::vector<ListNode *> &lists) {
    std::priority_queue<ListNode *, std::vector<ListNode *>, Compare> pri_queue;

    for (ListNode *v : lists) {
      if (v != NULL) {
        pri_queue.push(v);
      }
    }

    ListNode *head = nullptr, *tail = nullptr;
    while (pri_queue.size() != 0) {
      if (head == nullptr) {
        head = tail = pri_queue.top();
      } else {
        tail->next = pri_queue.top();
        tail = tail->next;
      }
      pri_queue.pop();

      if (tail->next != nullptr) {
        pri_queue.push(tail->next);
      }
    }

    return head;
  }

 private:
};

int main() {}
